2020年集成电路EDA设计精英挑战赛赛题指南

集成电路EDA设计精英挑战赛赛题指南

集成电路EDA设计精英挑战赛组委会   2020.6.29更新

赛题一：Synopsys篇

 

一、赛题名称

基于虚拟原型平台探索软硬件协同设计（Exploring HW/SW Co-Design with Virtual Prototyping）

二、赛题背景

现代soc集成了越来越多的功能，不仅在硬件，而且在软件方面，都变得越来越复杂。在硬件就绪后开发软件在业界已不再高效和具有竞争力。特别是在5G、人工智能、汽车和应用处理器等高速发展的垂直市场上，迫切需要采用虚拟原型技术并行设计软硬件。（Modern SoCs are getting more and more complicated as they integrate more and more functionality, not only in hardware (HW) side but also in software (SW). Developing SW after the HW ready is no longer efficient and competitive in the industry. There is a strong need to design HW and SW in parallel using Virtual Prototyping technology especially in the hot & fast paced vertical market of 5G, AI, automotive and application processors, etc.）

三、赛题描述

Synopsys的虚拟原型解决方案是虚拟开发工具包（VDK）。它是一种基于IEEE SystemC语言的transaction 级别仿真技术，能够运行实际的二进制软件image。我们会提供一个参考的AI-VDK，它由几个Arm Cortex A55s、GIC500、DDR&SRAM存储器、UART和Nvidia的开源AI加速器模型NVDLA-AI组成(www.nvdla.org). 这个VDK可以在不到一分钟的时间内启动Linaro Linux，并提供已经移植好的CNN网络示例，如AlexNet和ResNet。竞赛范围将以AI VDK为基础，利用现代仿真技术在该平台上运行复杂的人工智能网络，并实现仿真加速。对于每一项加速方法，速度提升快慢为衡量标准。 

以下是学生在竞赛中需要完成的目标任务：

1. 按照给定的指导步骤设置工具环境，创建并编译AI-VDK平台，然后运行AI-VDK启动Linux，执行AlexNet/ResNet并得到正确的结果。通常，AlexNet需要5~10分钟才能完成，ResNet需要20~30分钟，具体取决于不同的主机配置。

2. 在运行AlexNet/ResNet的同时，对AI-VDK仿真插入性能检测点并进行统计分析，找出NVDLA加速器模型中仿真速度的瓶颈； 

3. 提高AI-VDK的仿真速度。根据任务2的结果，探索以下不同的仿真技术，以加速NVDLA加速器模型的执行。根据应用的不同技术收集性能提升数据：

a. 子任务A：使用专门的x86（SIMD）指令来加速关键算法的计算功能。

b. 子任务B：使用OpenMP（Open Multi-Processing）加速关键算法的执行。

c. 子任务C：在主机中有独立的GPU卡，利用主机GPU加速计算密集型的算法部分，即主要的VDK仿真运行在CPU上，而模型中的一些关键算法部分会调用GPU运行加速。

d. 子任务D：根据给出的编码准则和简单示例，将VDK工具提供的多核仿真技术应用到NVDLA模型中。

Synopsys’ solution for Virtual Prototyping are Virtualizer Development Kits (VDKs). It is a transaction-level simulation technology based on the IEEE SystemC language, which can run the actual binary software images. We have a reference  AI VDK which consists of several Arm Cortex A55s, GIC500, DDR & SRAM memory, UART, and a model of the NVDLA AI accelerator, the open source AI accelerator from Nvidia (www.nvdla.org ). This VDK boots Linaro Linux less than one minute and provides ready ported CNN network examples such as Alex Net and Res Net. The competition scope will use the AI VDK as basis to gear up simulation speed while running complex AI networks in the platform using modem simulation techniques. 

Below are target tasks that students will need to work on during the competition:

1. Follow up the given instructions to setup tool environment, create and build the AI VDK platform, then run the AI VDK to boot Linux, execute AlexNet/ResNet to get correct results. Typically AlexNet takes 5~10 minutes to complete and ResNet takes 20~30 minute dependent on different host machine configurations.

2. Instrument and profile the AI VDK simulation while running AlexNet/ResNet, find out the hot spot or bottleneck of the simulation speed in the NVDLA accelerator model; 

3. Improve the simulation speed of the AI VDK. Based the results from task 2, explore below different simulation techniques to speed up the execution of NVDLA accelerator model. Gather performance gain data based on different techniques applied:

a. Subtask A: use specialized x86 (SIMD) instructions to speed up critical algorithm computational functions.

b. Subtask B: apply OpenMP (Open Multi-Processing) to speed up critical algorithm execution.

c. Subtask C: with a standalone GPU card in the host machine, utilize a host GPU to accelerate computation intensive algorithm part, i.e. the major VDK simulation runs on CPU, while some key algorithm part in the model will call GPU to execute the code for speed up. 

d. Subtask D: apply multi-core simulation technology provided by VDK tool to the NVDLA model with given coding guideline and simple example.

四、评分标准

任务1   正确理解任务，搭建平台和仿真环境                       40分

任务2   正确并高效设计分析仿真速度瓶颈的手段，找到仿真瓶颈点                                                            20分

任务3  实现SIMD 仿真加速，并提供加速比信息            10分

            实现OpenMP仿真加速，并提供加速比信息                     10分

             实现GPU仿真加速，并提供加速比信息                           10分

             实现VDK多核加速，并提供加速比信息                           10分

赛题二：华大九天篇

一、赛题名称

版图局部详细布线

二、赛题背景

        布线在物理设计流程中是非常重要的一个步骤，它将分布在芯片核内的模块、标准单元和输入输出单元按照逻辑关系进行互连，并且满足设计规矩，布线结果的好坏直接影响整个芯片的性能。近年来, 随着集成电路制造工艺的迅速发展, 芯片集成度和复杂性不断增加, 一块芯片所集成的线网数目不断增大且密度持续增高, 使得VLSI布线难度越来越大。不仅仅是因为线网增长的数量和规模，还有随之增长的可制造工艺约束规则，为了提高良率，这些DFM规则已经增长到成百上千，并且随着制造工艺节点持续增加。因此，设计能够处理海量级网表、并且满足先进工艺设计规则的布线器一直是EDA领域的核心问题之一。

三、赛题描述

1）总体描述：将版图内的模块、标准单元和输入输出单元（I/O Pad）按照逻辑关系进行互连，并且满足ERC、DRC和其他布线指标，如总线长、通孔数量等，如下图所示：

2）输入：若干个版图的原始LEF, DEF

3）输出：布线之后的DEF

4）LEF和DEF的说明：

a)  LEF： LEF(Library exchange format)是自动布局布线(APR)所必须的库文件，它主要分两个部分，Technology LEF和Cell LEF。Technology LEF里边包含工艺信息、设计规则信息、通孔信息等。Cell LEF中包含单元库中各单元的信息。

b)  DEF：DEF(Design exchange format)设计交换格式。这个文件中包含了电路的连接关系网表，并且描述了电路布局布线后单元及互连线的具体物理信息。输入DEF中将带有布局数据；输出DEF要增加布线结果数据。

5) ERC标准：

a)  OPEN：如果在net上的任意一个pin没有进行连接，则此net视为open。

b)  SHORT：如下图所示，两条不同NET短路

6）DRC标准：考察以下三种DRC

a)    Min Width，语法如：

LAYER M1
  TYPE ROUTING ;
  MIN WIDTH 0.06;

END M1

b)    Min Spacing，语法如：

LAYER M1
  TYPE ROUTING ;
  DIRECTION HORIZONTAL ;
  SPACING 0.06;

END M1

c)    Min Spacing，语法如：

LAYER M1
  TYPE ROUTING ;
  WIDTH 0.06;
   AREA 0.02;

END M1

7）基本流程如下：

8）提交要求：

其中执行码的命令行和参数要求为：

router.exe -lef input.lef –def input.def –result result.def-lef ：输入lef-def：输入def-result：输出def，包含布线结果

四、评分标准

a)   技术评分总分100分，每道题目均依据以下计分公式：

Score = basic_score * (1 + runtime_factor)来进行计算，Score越小得分越高，其中：basic_score为以下布线指标的加权和，布线指标将由我们提供的评测程序计算。括号中的数值为每项的权值。线长单位是M1的Pitch。

l  Open Net Number（10000）

l  Short Number（1000）

l  Number of min-spacing violations（1000）

l  Number of min-width violations（1000）

l  Number of min-area violations（1000）

l  Total number of vias（4）

l  Total length of wires（1）

l  runtime_factor的最大值为0.1，最小值为-0.1。公式为：

runtime_factor = min（0.1，max（-0.1，0.1 * log10（runtime / reference_runtime）））

其中reference_runtime为参考运行时间，每道题都有自己的参考运行时间；runtime为程序运行时间，多次结果挑选中间值。按照计算公式所述，如果布线器比参考标准快1倍或者慢1倍，则会获得大概3%的分数奖励/惩罚。

对于每道题目，所有队伍都要排名。分数越低，排名越高。最终计算每个队伍的平均排名值，排名值越低，技术评分越高。如下表所示：

b)     九天将根据评分规则的不足逐步改进规则，以利于提升比赛水平。

五、参考资料

1)  《Handbook of Algorithms for Physical Design Automation》

2)   《超大规模集成电路布图理论与算法》

3)   Dr-cu https://github.com/cuhk-eda/dr-cu

4)  Rsyn - x https://github.com/RsynTeam/rsyn-x

5)   CUGR https://github.com/cuhk-eda/cu-gr

6)   FastRoute https://github.com/The-OpenROAD-Project/FastRoute

赛题三：华大九天篇

一、赛题名称

智能MPW拼接

二、赛题背景

在IC的设计、制造等过程中，常常遇到模块拼接的情形，即对于给定数目的多个不同形状和尺寸的芯片版图（模块），根据给定规则，对其进行合理摆放，使得组合而成的矩形区域面积最小。

这个背景来源于多芯片的MPW拼接成一个曝光面积矩形（称为一次shot，即光刻机进行一次曝光的面积大小），需要求出最小的曝光面积，对于晶圆的利用率则最高。

在带有连接关系的版图自动布局布线中，其结果好坏的指标计算时间很长，对问题的求解形成障碍。求解方案需要考虑时间代价。而人工版图拼接的工作量负担沉重、且无论对于以上那种情形，利用率均难达最优。急需自动生成版图拼接技术。

该需求可以扩展到其他有关AI Placement的应用，前景十分广泛。

三、赛题描述

1）输入：给定N个不同形状和尺寸的多边形(相当于版图边界外形)，多边形为矩形或边均为正交方向的多边形。

2）求：最小的拼接面积

3）拼接规则：

a)  各多边形之间，允许间距为0，但是不允许两个多边形重叠（overlap）

b) 各多边形允许做基本的几何旋转（0°/90°/180°/270°/MX/MY）

c)  最终拼接的总区域外接矩形， 其50um ≤ 宽 ≤ 300um， 50um ≤长 ≤ 400um

4）难度升级：

a)      增加时间代价函数，每次计算面积，均自动等待指定时间（比如15分钟）才给出结果

b)      增加对拼接矩形形状的限制，即在相同的矩阵面积情况下，长宽比越接近1：1（也即越接近正方形）的矩形更优。这是因为IC制造过程中，如果一个shot越细长，意味着一次曝光中有半导体器件的几何距离越遥远，器件之间工艺误差可能会越大。

5) 举例：对以下4个多边形，只有如下的拼接方式（虽然必不可少也会造成一些面积浪费），能使得虚线框的面积最小。

6）基本流程说明：

7）提交要求：

其中，对可执行程序prai.exe的要求是：

a)      Linux 服务器环境上可以正确执行

b)      执行示例：prai.exe  /xxx/xxx/ inputfig.txt

c)      输出：/xxx/xxx/result.txt

d)      说明：

    输出文本和输入文件在同一目录下

            输出文本命名有要求，必须是result.txt

8) 求解思路猜想：

a)      爬山、局部搜索、蚁群算法、遗传算法、模拟退火等

b)     动态规划

c)      贝叶斯优化（Bayesian Optimization）

d)     强化学习

e)     参考文献，见本文最后章节

四、评分标准

每个程序的技术评分为100分，其中：

◆总面积占40分：收集程序运行所有case的总面积进行排序。依据排序结果取前十个值（面积值相同时作为并列处理），分为满分40分、35分、30分、28分、26分、24分、23分、22分、21分和20分给分。其余情况计为0分。

◆运行时间占20分：收集程序运行所有case的总时间（精确到毫秒）进行排序。依据排序结果取前十个值（时间相同时作为并列处理），分为满分20分、17分、14分、12分、10分、9分、8分、7分、6分和5分给分。其余情况计为0分。

◆运行内存占20分：收集程序运行每个case的内存峰值的和（精确到兆字节）进行排序。依据排序结果取前十个值（值相同时作为并列处理），分为满分20分、17分、14分、12分、10分、9分、8分、7分、6分和5分给分。其余情况计为0分。

◆拼接矩形形状占20分：计算程序运行每个case的输出结果的外接矩形的长宽比与目标矩形长宽比的偏离值（保留2位小数，取绝对值），将程序所有case的偏离值的和进行排序。依据排序结果取前十个值（值相同时作为并列处理），分为满分20分、17分、14分、12分、10分、9分、8分、7分、6分和5分给分。其余情况计为0分。如果矩形形状超出了50um ≤ 宽 ≤ 300um， 50um ≤长 ≤ 400um的限制，此项直接给0分。

◆九天将根据评分规则的不足，逐步改进规则，以利于提升比赛水平。

赛题四：芯华章篇

一、赛题名称

时序模块驱动冲突的检查

二、赛题描述

在RTL的设计中，有一部分是组合逻辑(combinational logic)，一部分是时序逻辑(sequential logic)。一般而言， 时序逻辑的每个输入只能有一个驱动（driver），该驱动可以是组合/时序逻辑的输出。 如： 

在实际RTL开发中，有一类比较常见的错误，就是一个时序电路的输出（如Q）会有多个驱动，如：

always @(posedge clk)

Q <= A & (B | C);

always @ (E)

Q = E;

通常，这种错误往往在仿真结果出现问题的时候才能发现, 用户调试起来周期非常长，尤其是RTL设计非常大的时候。理想的情况是验证工具进行静态检查(static check)， 让这类问题在编译阶段(compile time)报出，从而节省用户的调试时间。本赛题就是要求参赛者开发这样一种静态检查的功能。

三、驱动冲突的规则

1、驱动冲突的检查对象是变量（variable）， 而非wire（net type）, 因为IEEE标准已经确保了wire是不能用被时序电路驱动的。变量的类型包括reg, integer 等。

2、驱动冲突的检查模块是always block. 在其他scope下，多个驱动是允许的。如两个initial block里驱动同一个变量是合法的. 但是同一个变量同时被一个initial block 和 always block 驱动就是有冲突的。

3、在同一个always block中的多次写操作不视为驱动冲突

always @(posedge clk)  begin

  if (sel)

Q <= D1;

  else

Q <= D2;

end

四、测例描述

RTL设计以Verilog形式，如：

1: module dut (input a, b, c, e, output q);

2:  wire a, b, c;

3：reg r;

4：reg clk;

5：reg q;

6：reg d;

7：always @(a, b, c)

8：d = a & (b | c);

9：always @(e)

10：q = e;

11：always @(posedge clk)

12：q <= d;   

13: endmodule

输出：

 屏幕上需要打出如下报错信息（至少两个）

 The following drivers conflict:

 Line 10

 Line 12

五、开源代码

可以下载开源的Verilog simulator http://iverilog.icarus.com/home

并在这个基础上开发所需的功能

六、评分标准

评分标准包括功能的覆盖程度、代码质量、测试，及性能等几部分

1、功能覆盖及质量 （80分）

1） 基本功能(20分)

支持scalar type (reg 等), 以各种driver 类型，

2) 支持vector/memory , 以及select （30 分）

      E.g.

      reg [3:0] aa

             always @(bb)

             aa[0] = bb;

always @(posedge clk)

aa[1] = cc;

这个例子应该是没有冲突的，因为他们的select 不同

而下面这个会在a[1]有冲突：

      always @(bb)

             aa[1:0] = bb;

always @(posedge clk)

             aa[3:1] = cc;

3）支持for loop分析  (30 分)：

 ◆支持单层的for loop （15 分）

reg [0:7] aa;

        reg [0:7] bb;

    reg [0:7] cc;

always @(posedge clk)

             for (i = 0; i < 4; i++)

                 aa[i] <= cc[i]

        always @(posedge clk) begin

            for (i = 3; i < 8; i++)

                     aa[i] <= bb[i];

        end

  

这里，aa[3] 是有冲突的, 其他位没有冲突

◆支持嵌套的 for loop (15 分)

  reg [0:7] aa [0:15];

always @(posedge clk)

for (i = 0; i > 7; i++)

           for (j = 0; j < i + 1; j++)

               aa[i][j] = cc;

always @(posedge clk)

       for (i = 0; i > 7; i++)

           for (j = i+1; j < 15; j ++)

               aa[i][j] = bb;

以上两个是没有冲突的

2、代码及测试 （10分）

主要评估标准：

◆选手代码的整洁程度，可读性，可调试性

◆对原开源源代码的改动在满足性能/功能的前提下，要尽可能的小（避免重复开发而导致质量问题）

◆是否有测试方案以确保软件的正确性

3、性能 （10分）

  根据一组提供的benchmark， 以compile time（CT）为衡量依据。性能超越80%参赛选者得10分，性能超越50%参赛选手者得5分。

4、附加题 （20 分）

Verilog 有一种概念是 hierarchical reference , 即从一个module可以访问定义在另一个module的 variable. 例如：

module top;

     sub s0();

     wire r;

   endmodule

module sub;

     wire w;

     assign top.r = w;  //hierarchical reference

endmodule 

 其对应的概念是：

如果 ‘sub’ module在’top’ 下面有多个instance , 会造成’r’ 有多个驱动。

完整的例子如下：

1: module top;

2: reg q;

3：submod s1();

4：submod s2();

5：endmodule

6: module submod();

6：reg d, clk;

7：always @(posedge clk)

8：top.q <= d;

9：endmodule 

由于这个驱动在源代码中只有一处，为了给用户更多信息，需要把这个驱动所在的hierarchal path 打出来： 

The following drivers conflict:

 Line 8， in instance top.s1，  

 Line 8,  in instance top.s2

七、测试集

比赛开始时，将提供50个左右单元测试供参赛选手使用。

  验收时，将在另外一个测试集 （100-200个case）中测试选手的提交的软件，以通过率作为功能覆盖率（5.1）的打分标准。另外，会有一个性能测试集（20个左右benchmark）, 作为性能（5.3）的打分标准。

八、技术指导

   对于不熟悉Verilog 以及 iverilog开源软件的选手，可以提供一定的技术指导，使选手可以尽快进入核心功能开发阶段。

九、参考资料

  1) IEEE1364 Verilog Standard

  2) Iverilog : http://iverilog.icarus.com/home

赛题五：华为海思篇

一、赛题名称

基于分布式计算框架的自动测试向量生成算法

二、赛题背景

1、概述

在VLSI电路的设计过程中，DFT是保证回片测试质量的重要手段，TPG（Test Pattern Generation）是其中一个重要的环节。随着电路规模的增大、设计复杂度的提升和先进工艺演进，高效率、高质量的产生测试向量变得更加困难。

ATPG（Automatic Test Pattern Generation）是整个TPG Flow中的核心组件，一个好的工业级ATPG算法应能够在更短的时间内，产生更少的测试向量数，并获得更高的测试覆盖率，使得测试成本更低。多年以来，业界针对ATPG有着持续研究，从布尔差分法、GF二值算法^[1]将电路模型转换成数学模型来生成测试向量，到D算法^[2]及其改进算法PODEM^[3]、FAN^[4]等基于故障激活的测试向量生成算法，以及BDD、SAT-Based ATPG算法^[5]，持续努力在寻求新的算法方案以达到高效率、高质量的测试向量。

然而，随着电路规模的日益增大，TPG Flow的性能逐渐成为瓶颈，主要表现在算法的效率和内存两方面。在算法上的优化探索不能十分有效地解决问题。传统的数据计算和数据存储方式已经无法满足要求。为解决内存和效率问题业界提出了分布式的解决方案。MapReduce^[6]是当前较为成熟的开源分布式计算框架，Hadoop和Spark是MapReduce框架的两个比较有影响力的实现。Hadoop的核心组件包括Hadoop Distributed File System（HDFS）、Hadoop MapReduce等模块，其中HDFS完成数据的分布式存储，Hadoop MapReduce完成数据的分布式计算。而Spark不同于Hadoop的是其job的中间输出和迭代结果可以保存在内存中，从而可以获得更高的数据访问速度。同时，结合Redis高性能数据库，在提升TPG中的静态数据的读取速度方面有较大可能性。综上所述，分布式计算框架与Redis的结合来实现TPG Flow，是当前解决TPG Flow性能瓶颈问题的值得探索方向之一。

2、传统的TPG流程

芯片在制造过程中，总会受到各种不确定因素的影响。比如，环境干扰、硅片质量不佳、机台设置偏差、工程师操作失误等等，我们实际制造出来的芯片总会存在各种缺陷。

如图1所示，如果电路的e点对电源短路，我们可以将这一电路缺陷抽象为名为stuck-at-1的fault model。电路表现为不论a，b的输入如何变化，e点电平始终为1（即高电平）。在芯片量产测试的ATE机台上，为了检测到这个芯片内部的缺陷，我们只能通过对输入a，b施加特定的激励，捕获并检测输出g的电平与预期的电平是否一致，以推断电路是否存在缺陷（可能是由于e点的stuck-at-1故障导致）。举个例子，当电路的e点出现对电源短路故障时，如果对a，b施加激励（a = 0, b = 1），此时，g的预期输出为0。但是，由于e点存在类型为stuck-at-1的fault，因此实际输出为1。因此，我们称e点的stuck-at-1 fault能被pattern（a = 0, b = 1）检测到。

图1

在集成电路中，对指定的fault产生pattern的过程，称为测试向量产生（Test Pattern Generation，缩写为TPG）。本赛题仅针对组合电路的stuck-at fault的向量产生。由于电路中的每一个点都有可能存在fault，我们可以通过解析电路网表得到完整的fault集合，称为fault list。由于ATE的测试成本非常高，因此如何针对指定电路的fault list生成一组尽可能少的pattern集合是TPG需要解决的问题。

一个传统的TPG流程^[7]如图2（组织方提供该flow的源码和说明文档，C++实现，参赛者基于对源码的理解实现自己的并行flow）所示。首先，解析网表并得到netlist；根据netlist生成完整的faultlist集合；选择部分fault做测试向量生成；然后，经过fault simulation验证pattern正确性。如果这些pattern能够检测到除了被选择的之外的fault，则将这些fault一起标记为tested。循环此过程，直至所有的fault被选择。如果最终得到的pattern能够标记tested的fault个数除以fault的总个数，就是这组pattern针对该网表的覆盖率（coverage）。覆盖率是评价一组pattern的好坏的重要指标之一。

                                              

3、传统的TPG算法的问题与分布式计算的优势

TPG是一个NP-Complete问题，且传统的TPG Flow往往采用前述的串行迭代的计算方式。随着芯片技术的不断进步，芯片集成电路规模在快速增加。对超大规模集成电路的执行测试向量产生的计算，不仅计算量十分巨大，还需要巨大的内存资源。这不仅导致测试向量的生成过程十分耗时，还导致在单台计算机资源难以支撑巨量的内存消耗，最终会导致测试向量无法生成。

当前IT领域已经步入云计算的时代，以云计算为基础设施的分布式计算架构，可以同时利用多台计算机的计算资源来完成大规模的计算任务。与传统的单机处理模式相比，分布式计算架构在单位时间内可以拥有更高的信息处理速度、算力扩展性和更多的内存资源。理论上，分布式计算架构可以很好的解决传统的TPG Flow的高算力和高内存的诉求。

4、TPG与MapReduce结合的新思维

MapReduce是一种编程模型，用于大规模数据集的并行运算。它借助于函数式程序设计语言Lisp的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了抽象的操作和并行编程接口，以简单方便地完成大规模数据的编程和计算处理。

MapReduce的工作原理如图3所示。MapReduce主要分为两个计算阶段：

◆ Map阶段

Map阶段由一个或者多个MapTask组成。每个MapTask处理输入数据集合中的一片数据(InputSplit)，如下图中的split 0~ split 4。并将计算结果（同样是多个数据片段）写到本地磁盘上。

◆ Reduce阶段

Reduce由一个或者多个ReduceTask组成。ReduceTask则从每个MapTask上远程拷贝相应的数据片段，经分组聚集和归约后，将输出数据回写到HDFS上作为最终结果。

我们可以利用Hadoop的MapReduce组件来完成ATPG的计算。为此，我们可以把ATPG模块放到Map任务中，并将fault list放到HDFS上。由框架自动实现fault list切分和任务调度。由于每个ATPG任务需要在生成测试向量的过程中使用网表的连接关系，我们可以考虑将网表信息存到Redis数据库中，以支持多节点的快速访问。在Reduce阶段，获取生成的pattern以便执行后续处理，比如精简Pattern等。由于Hadoop的MapReduce组件会涉及大量的HDFS文件读写，在处理迭代式计算时显得力不从心，因此如果想实现一个多轮迭代式的TPG flow，还可以使用类似于Spark的内存计算框架。

三、赛题描述

1、赛题描述

本课题需要参赛队伍基于给定的ATPG算法完成一个分布式的TPG系统，并期望达成下列几个基础的技术目标：

（1）    基于MapReduce的分布式的TPG系统。

（2）     从软件的算法、流程、系统架构等方面优化系统以获得更优的技术指标。

本赛题的总体方案如图4所示：

◆赛题Case

赛题Case为系统输入之一，该部分由出题方提供。参赛队伍也可自行构造一些Case，便于验证和优化自己的算法和系统。

◆分布式TPG系统

构建分布式的TPG系统为本赛题的核心任务。出题方会提供简单的搭建指导，参赛队伍需要实现环境自动搭建脚本，用于将自己实现的环境从无到有自动搭建出来。

◆ATPG算法

ATPG算法也是整个系统的核心，该部分出题方会开源可以构建和运行的基础代码。但该算法并非最优化，需要参赛队伍大胆创新和优化。

◆Pattern集

Pattern集为系统输出，是一组Pattern集合，出题方仅会给出基准Pattern总数和TPG的基准运行时间。参赛队伍利用自己实现的算法和系统生成Pattern集。

算法基础源代码及竞赛用例等相关资源可参见下列代码仓库。关于算法和系统的优化思路，可参考Q&A。

https://gitee.com/openeda/OpenTPG

2、  竞赛规则

下面为该课题竞赛流程：

图5

各参赛队伍需要以赛题提供的在线代码库为基础，通过自己的知识、技能、实践和创意来实现一个新的分布式TPG系统。

为尽量排除环境干扰，在作品评测阶段，会连续运行三次，取平均成绩。

源代码

考虑到从零开始完整实现一个TPG Flow软件，是有一定难度和工作量的，我们建议参赛队伍都以已经开源的源代码为基础进行修改和增强。除非您的队伍有信心，否则您应该避免完全重新开发全部源代码。

竞赛Case

出题组会提供4套竞赛Case，用作日常调测和竞赛比分。其中，3套为常规Case，1套为挑战Case。各Case有难易程度之分，相应地会有不同的评分权重。各Case的评分权重和计分方式，可参见后文的"评分标准"章节。

接口

请仔细阅读开源代码的README，请勿随意修改系统的接口。整个基础代码里面接口有两类：一类是源代码算法接口；另一类是系统环境搭建脚本；README里面有详述。

环境

构建环境和运行环境采用的系统版本一致。建议各参赛队伍也在该环境下开发和测试。具体的构建和运行环境信息，以及各构建工具链、依赖组件版本等信息均可参见源码仓库的README。

四、评分标准

1、技术评分，共80分

技术点评分标准

技术评分的主要的评价标准是TPG系统的性能的几个核心技术指标。本竞赛项目我们只关注TPG系统的输出的Pattern的覆盖率、Pattern数、运行时间这三项技术指标。这三项技术指标有一定的约束关系：

◆覆盖率，决定了系统输出的Pattern的质量，是所有TPG系统中的各项技术指标中最关键的要素。如果输出的Pattern的覆盖率不达标，即使Pattern数再少，运行时间再快，也将失去价值。

◆Pattern数，决定了系统输出的Pattern的测试成本。如果测试成本太高，那么这些Pattern将无法交付使用。

◆运行时间，是影响芯片交付周期的关键因素之一。更短的ATPG运行时间，能够加快芯片的研发速度，芯片可以更快上市。

以下为我们关注的主要技术指标以及评分标准：

（1）      覆盖率，40分

所有Pattern的总覆盖率是ATPG基本要求，我们认为覆盖率不达标的Pattern是没有价值的。不同覆盖率的评分方式如下：

Ÿ   覆盖率达到或者高于95%：40分

Ÿ   覆盖率低于95%：0分

（2） Pattern数，20分

TPG最终所产生的Pattern数越少越好。考虑到不同的Case，其网表Pattern的数量都是有差距的，所以每个网表都会有一个基线Pattern数。具体评价标准如下：

Ÿ   Pattern数小于基线值的0.5倍：20分

Ÿ   Pattern数为基线值的：[0.5,0.6)倍：15分

Ÿ   Pattern数为基线值的：[0.6,0.7)倍：10分

Ÿ   Pattern数为基线值的：[0.7,0.8)倍：5分

Ÿ   Pattern数大于或等于基线值0.8倍：0分

（3） 运行时间，20分

TPG的运行时间越短越好。考虑到不同的Case，其TPG的计算时间是有差距的，所以每个网表都会有一个基线运行时间。具体评价标准如下：

Ÿ   运行时间小于基线值的0.4倍：20分

Ÿ   运行时间数为基线值的：[0.4,0.5)倍：15分

Ÿ   运行时间数为基线值的：[0.5,0.6)倍：10分

Ÿ   运行时间数为基线值的：[0.6,0.7)倍：5分

Ÿ   运行时间大于或等于基线值的0.7倍：0分

技术评分总分计算方式

技术评分环节由多个Case组成，每种Case会有不同的电路特点，用以验证参赛队伍搭建的TPG系统的对不电路特性的适应能力。所以，各参赛队伍应该避免设计方案过于偏向特定电路。每个Case的各技术分评分会单独评分，技术评分总成绩有各Case的技术评分的加权和来决定。下面为每个Case的评分权重为：

Ÿ   Case 0：10%（常规）

Ÿ   Case 1：30%（常规）

Ÿ   Case 2：40%（常规）

Ÿ   Case 3：20%（挑战）

我们设定case“i”的评分权重为p(i)，每个Case的覆盖率得分为c(i)，Pattern数得分n(i)，运行时间得分t(i)，那么技术评分总分计算公式为：

                                              

2、设计报告，共20分

行文要求条理清楚，详略得当，清楚易读，内容应该包括以下几个方

（1） 架构描述、问题分析、算法优化原理描述，共10分

（2）  方案创新性，共10分

五、参考文献

[1] Rolf Drechsler,Stephan Eggersglüß,Görschwin Fey,Daniel Tille.Test Pattern Generation using Boolean Proof Engines.

[2] J.P.Roth,W.G,Bouricius,and P.R.Schneider.Programmed Algorithms to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits,IEEE Transactions on Electronic Computers.

[3] Prabhakar Goel.PODEM-X:AN AUTOMATIC TEST GENERATION SYSTEM FOR VLSI LOGIC STRUCTURES

[4] H.Fujiwara.FAN:A Fanout-Oriented Test Pattern Generation Algorithm.In Proceedings of the IEEE International Symposium On Circuits and Systems,pages 671-674,July 1985.

[5] Armin Biere,Wolfgang Kunz.SAT and ATPG:Boolean engines for formal hardware verification.

[6] MapReduce:Simplified Data Processing on Large Clusters.

[7] ELEC 516 VLSI System Design and Design Automation Spring 

      2010 Lecture 10 – Design for Testability. https://www.slideserve.com/danton/elec-516-vlsi-system-design-and-design-automation-spring-2010-lecture-10-design-for-testability

六、Q&A

1、Q：ATPG算法对于覆盖率和pattern数的影响？

ATPG的算法本质上属于NP-Complete问题，该算法的优化总的来讲就是尽量缩小搜索空间和减少backtrack的次数。实际使用时通常会限制最大backtrack的次数，好的算法应在该限制之内尽可能提高产生test cube的成功率，该成功率最终变现为生成pattern集合的故障覆盖率。由于一个pattern通常能detect多个fault，因此好的算法应该能产生更高质量的pattern（more specified bits），用更少的pattern数量去获取目标覆盖率。

Cube的定义：ATPG产生的向量会对一部分primary input指定值，另外一部分为X态（do not care），此时的向量成为cube，cube经过random fill或者其它算法对剩余的primary input赋值后的向量成为pattern。

2、Q：并行对于pattern数量的影响？

使用并行意味着可以获取更多的算力，在同样的时间内可以target更多的fault来生成cube，对这些cube做合并和剔重等操作，更易于获取高质量的pattern，从而减少最终的pattern数量。

3、Q：关于减少Pattern数和运行时间有哪些典型的方法？

ATPG中可以优化的点是非常多的，也是该行业的研究热点，典型的优化思路有：

（1）    将多个不同的Cube按照一定算法进行合并，可以直接减少Pattern的数量；

（2）     在Fault Simulate之后，执行清除冗余Pattern的操作，可以进一步减少Pattern的数量；

赛题六：概伦电子篇

一、赛题名称

快速电路仿真器（FastSPICE）中的高性能矩阵向量运算实现

二、赛题背景

在晶体管级电路瞬态仿真过程中，仿真器需要根据电路连接关系并结合KCL、KVL定理建立微分方程，然后求解离散化的方程，中间每个步长输出电压和电流的仿真结果。在瞬态仿真中的每个步长都会涉及到大量的矩阵向量运算，例如电流输出的计算，需要计算很多条支路电流并求和。矩阵向量运算在整个仿真中占据了相当比例的仿真时间，尤其是针对存储器（memory）电路的快速电路仿真器（FastSPICE）。因此，加速矩阵向量运算可以直接提高电路的仿真速度。

电路方程的矩阵大小与电路的节点个数成正比，比如，大型的存储器电路（DRAM, Flash, SRAM等等），其维度可达到1000万以上，如此高维度的矩阵以普通二维数组的方式存储会消耗巨大的内存。由于电路的每个节点通常只与少数节点有连接关系，因此电路方程矩阵通常是稀疏度很高的稀疏矩阵。稀疏矩阵特有的存储方式仅包含矩阵中的非零元素，可大大减少内存的消耗量，为存储高维度的矩阵提供可能。稀疏矩阵的矩阵向量运算与普通的矩阵向量运算略有不同，对整体运算速度有较明显的影响。

希望参赛者能够开发一种针对电路方程的高效矩阵向量运算方案和实现，减少运算时间，从而提高电路仿真速度。

三、赛题描述

1、概伦电子提供电路方程矩阵的数据接口和计算方法，参赛队开发高效矩阵向量运算的实现，并以动态库的形式提供。电路仿真器在执行指定电路网表仿真时会加载该动态库，并将相应的电路仿真矩阵向量运算通过预定接口传递给动态库，由参赛队开发的高效矩阵向量运算架构完成。电路仿真器在仿真中会反复地产生不完全相同的运算任务，而且在同一时刻会向动态库提供多个矩阵的向量乘运算任务。动态库在完成运算任务后需要将结果写入到接口指定的数据块中，然后电路仿真器继续其他任务的执行。参赛队可以采用并行、指令优化等多种高性能计算相关的优化方法对运算过程进行加速，以实现用更短的时间得到正确结果的目标。

2、本赛题要求参赛队完成快速电路仿真器 (FastSPICE)中的相关支路电流计算任务，其中电路元件的电导将构成N×1阶稀疏矩阵，节点电压组成N×1阶矩阵，其计算过程包含以下矩阵运算：

图1

3、在电路仿真中，电路仿真器会在每个仿真点产生一次计算任务，每次计算任务包含多块N×N阶稀疏矩阵与N×1阶矩阵的运算的子任务，不同块之间矩阵向量运算是独立的。每次计算任务包含的矩阵块数是相同的，而且矩阵的维度和非零元的位置是不变的，但非零元的数值会发生变化。电路仿真器会根据电路的工作情况，只对矩阵或向量的某些行列进行运算，该信息可通过给定函数接口获取。电路仿真器会在每个仿真点通过调用指定的动态库函数接口将每次计算任务的所有矩阵按分块的形式给出，参赛队需要在动态库内完成的所有矩阵的运算任务，并将结果写入指定内存区域，然后返回。电路仿真器在动态库函数返回后再进行后续的电路仿真。

4、竞赛基本流程如下图：

四、评分标准(最终解释权归概伦电子所有）

技术评分（共100分）

1） 精度

确保双精度数据类型计算正确，如果错误，总分直接计0分。

2）  速度（60分）

根据参赛队伍的数量排名，每个排名之间相差5分。不同测试用例的权重不同，综合速度第一名为60分，以第一名的速度为基准，其它参赛队作品的速度比这个基准慢10%以内的得55分，以此类推，20%以内的得50分，30%以内的得45分，40%以内的得40分，50%以内的得35分，60%以内的得30分，70%以内的得25分，80%以内的得20分，90%及以上的得10分。

3）  内存消耗（30分）

对同等测试用例下不同参赛作品的内存消耗量做归一化，按照与最优值的差距比例进行评分。综合使用内存量最小的作品得满分30分，以此为基准，其他参赛队作品的内存消耗量每比基准多10%，则减1分，直到扣完30分为止。假如基准为100MB，则内存消耗量为110MB的得29分，内存消耗量为150MB的得25分，内存消耗量为200MB的得20分，内存消耗量为300MB的得10分，内存消耗量为400MB及以上的得0分。

4）  创新项（10分）

依据报告中加速算法创新点的数量，以及对未来改进的展望进行评分。

赛题七：思尔芯篇

一、赛题名称

图分割算法（数字集成电路设计方向）

二、赛题背景

随着计算技术的发展，大数据时代的到来，超大规模图的分割问题越来越引起人们的关注，并被广泛应用于大数据处理的各个领域，如分布式计算问题划分、推荐策略、布局等等。

典型应用有超大规模数字集成电路仿真验证中的多FPGA系统分割，通过不同的分组权重将图分割成若干分组，进而实现快速高效的系统验证。

三、赛题描述

对给定的数字集成电路门级电路的网表文件，按照分组权重约束条件 - PIO / LUT / FLIPFLOP / CONNECTION / FIX-ASSIGN，对网表进行不同模式的Partition算法分割，分割成若干个分组。在保证整个图拓扑结构不变和满足约束条件的情况下，确保每个分组之间互联线数目最少。

 涉及知识点：

·        门级电路的图论建模

·        最小割相关min-cut算法

数学原理：

Partition算法的目的是对一个带顶点权重与连接权重的图, 根据设定的分组权重约束条件，进行不同的切割尝试，最后获取到一个最小的连接权重值的切割过程。

例如：对左下图进行切割，约束条件要求分为 2个分组，每个分组资源权重不限，一个分组包含节点5，另一个分组包含节点4,  则最优的切割结果为右下图， 互联线权重为5 < 2+2+1 >。 

 

技术评分点：

·        不同权重约束条件和不同工作模式下分割结果的正确性（主办方提供检查程序）

o   满足资源约束

o   网表等价（节点互连结构等价）

·        分割结果的最优化

o   Cut size（互联线权重）最小

·        满足分割结果正确的前提下，在同一平台（主办方将给出操作系统版本和编译器版本）上的运行时间，即所需的CPU算力

·        内存使用量

使用top命令或工具memtime

·        附加Benchmark测试（隐藏测试）的完成度

注：参赛队伍提供技术报告（含时间空间复杂度分析）、可执行程序与源代码

四、评分标准

技术评分，共100分。

1. 基础任务 – 60分 。（Benchmark测试的完成度占比70%，结果正确性、最优化、运行速度、内存使用量指标占比30%）

2. 高性能任务 – 40分。（Benchmark测试的完成度占比70%，结果正确性、最优化、运行速度、内存使用量指标占比30%）

说明：相关FAQ解答指南请联系eda_ec@s2cinc.com。

附件：赛题接口文件说明

1.1   输入文件

输入文件包含当前图(Graph)里面所有节点(Node), 连线(Net), 权重(Weight)和 分组(Group)的资源信息, 要求参赛者的分割工具根据这些信息对图中的节点进行切割, 根据实现算法的最优结果, 生成输出若干个小图.

·       Node definition file <节点定义文件 design.are>

每个节点名称以字母g和一个不重复的数字组成，

每行表示一个节点的资源信息，包含10种资源，每种资源权重以10进制数值表示。

<node> PIO INT FF LUT BUFG TBUF DCM BRAM DSP PPC [timing-property-list]

各个资源的定义如下表。

例如，

      常规节点文件，

g0   0 1 200 0 0 0 0 0 0 0

g1   0 1 200 0 0 0 0 0 0 0

g2   0 1 200 0 0 0 0 0 0 0

g3   0 1 200 0 0 0 0 0 0 0

g4   0 1 200 0 0 0 0 0 0 0

g5   0 1 200 0 0 0 0 0 0 0

 

带timing属性的节点文件，

g0   0 1 200 0 0 0 0 0 0 0 {ff}

g1   0 1 200 0 0 0 0 0 0 0 {c0}

g2   0 1 200 0 0 0 0 0 0 0 {c2}

g3   0 1 200 0 0 0 0 0 0 0

g4   0 1 200 0 0 0 0 0 0 0 {ff c2}

g5   0 1 200 0 0 0 0 0 0 0 {ff c2c3}

 其中,  [timing-property-list] 为可选性，里面属性定义如下，

ff           节点为ffd类型

c0         节点含有名为 c0的clk属性

c2c3     节点含有名为 c2和c3 2个clk属性

  Net definition file <连线定义文件 design.net>

 每个连线信息由2个或更多节点组成，一个为驱动节点(driver)，其他为负载节点(load),

每行表示一个连线的部分信息，格式如下，

 <node> <s/l>  [weight]

 s 含有驱动(driver)节点的连线部分

l 含有负载(load)节点的连线部分，一个连线可能含有一个或多个负载部分

weight 连线的权重值, 可选

 例如,

g1 s 1

g0 l

g0 s 1

g2 l

g1 l

  The FPGA group resource list file <FPGA 资源文件定义 design.info>

 Fpga 分组的资源定义与节点资源一致，每一行表示一个分组的资源最大权重值信息和分组的序号。

格式如下，<FPGA> PIO INT FF LUT BUFG TBUF DCM BRAM DSP PPC [int-list]

 其中，[int-list] 为可选性，

采用list列表表示，每个分组的序号(从1开始)，对应列表中相应的位置元素(从第1个元素开始)。列表里面的值表示当前分组与其他分组的互连线约束权重值。

每个分组的内部互联权重值为0，不用考虑。

第2列INT的值是最后list的和，如下800 = 0+200+200+400

分割算法必须根据分组资源信息对图中节点进行分割，输出的结果不能够超出每个分组的资源权重值。

例如2个分组，

FPGA 576 890 427200 427200 24 2048 24 55562240 0 0

FPGA 576 890 427200 427200 24 2048 24 55562240 0 0

4个分组，

      FPGA 576 800 427200 427200 24 2048 24 55562240 0 0   { 0 200 200 400 }

FPGA 576 800 427200 427200 24 2048 24 55562240 0 0   { 200 0 100 500 }

      FPGA 576 900 427200 427200 24 2048 24 55562240 0 0   { 200 100 0 600 }

FPGA 576 1500 427200 427200 24 2048 24 55562240 0 0 { 400 500 600 0 }

 The fix or preassigned node list file <预先分配的节点定义文件 design.fix>

 预先定义的节点分配文件，一行一个或多个节点在指定分组里面的分配信息。

分割算法必须根据节点预分配信息对图中节点进行分割，输出的结果满足所有预分配的节点分组信息。

注： 这个是优先级最高的规则，分割分组结果必须满足此文件预定义的分组

格式如下,

<FPGA TYPE mm>: <node> <node> ...

 mm分组编号是从1开始的正整数，不一定是连续的数字定义.

 例如,

FPGA TYPE 1: g0

FPGA TYPE 2: g1

例如，编号不连续的预分配定义，

FPGA TYPE 1: g0

FPGA TYPE 2: g1

FPGA TYPE 3: g3013

FPGA TYPE 4: g6026

FPGA TYPE 7: g30

FPGA TYPE 8: g40

 l The cut mode <分割模式>

 目前定义的分割算法的工作模式，

--fix-mincut  默认分割模式，所有的资源权重都是固定不变的，要求分割算法，能够在不超出分组资源权重的前提下算出最优的结果，且所有分组的对外互联数目总和最小。

--int-mincut  同 --fix-mincut, 此外，额外要求分割算法满足每个分组之间的互联权重约束，得出最优解，且所有分组的对外互联数目总和最小。

--ffd-mincut  同 --fix-mincut, 此外，额外要求分割算法满足每个分组flipflop驱动规则的情况下，得出最优解，且所有分组的对外互联数目总和最小。

   Flipflop 驱动规则如下:

1. 每个可分割的节点必须为带有ffd 属性的节点，或者其他节点，仅当它所有的驱动连线都为带ffd属性的节点。

2. 每个分组的节点必须由其他分组的ffd节点驱动.         

                                                                                      

1.2  输出文件

输出文件包含对图中所有节点进行分割后的最优分割结果和报告信息。

◆The output partition result file <分割结果文件 design.output>

分割结果文件，由分割算法根据当前的分割策略和模式运算得出的最优结果。

每一行包含一个分组信息里面包含的节点列表，以 'FPGA+序号 分组+mm' 字串开始，每个节点之间以空格隔开，每行建议最大包含20个节点，可以多行表示。

格式如下,

<FPGAnn TYPE nn>: <node-list>

例如,

FPGA1 TYPE 1 :g0 g1 ..... g19

                           g20 g21 gp0

FPGA2 TYPE 2 :g100 gp1 gp2

◆The output partition report file <分割结果报告文件 design.rpt>

分割结果报告文件，包含分组的实际资源权重使用值，以及每2个分组之间的互联信息。

只有2分组的情况下，{int-list} 不需要。

格式如下,

<FPGAnn TYPE nn>: <resource-list> [int-list]

{int-list} 采用list列表表示，每个分组的序号(从1开始)，对应列表中相应的位置元素(从第1个元素开始)。列表里面的值表示当前分组与其他分组的互连线约束权重值。

每个分组的内部互联权重值为0，不用考虑。

 例如,

2个分组的报告文件,

FPGA1 TYPE 1: 1 401 109 1814 0 0 0 0 0 0

FPGA2 TYPE 3: 2 401 0 4000 0 0 0 0 0 0

4个分组的报告文件件，

FPGA1 TYPE 1: 1 400 109 1814 0 0 0 0 0 0  { 0     200  50   150  }

FPGA2 TYPE 2: 2 350 0 4000 0 0 0 0 0 0      { 200 0      50   100 }

   FPGA3 TYPE 3: 1 200 109 1814 0 0 0 0 0 0 {  50   50    0    100 }

   FPGA4 TYPE 4: 2 350 0 4000 0 0 0 0 0 0      { 150  100  100 0    }

◆关于FPGA 编号和TYPE 编号

FPGA 后面的编号n 仅仅表示一个处理序号，不是分组号。一般情况下代码处理时fpga后编号和Type后分组号一致。比如design.output， design.rpt文件格式。如果不一致，以TYPE后编号为准（分组号）

如果fpga后无编号，以TYPE后编号为准，作为分组号。比如design.fix格式。

FPGA TYPE 1: g0

FPGA TYPE 2: g1

FPGA TYPE 3: g3013

FPGA TYPE 4: g6026

FPGA TYPE 7: g30

FPGA TYPE 8: g40

赛题八：安路篇

一、赛题名称

赛题名称 FPGA芯片的布局合法化

二、赛题背景

可编程逻辑模块（PLB）是FPGA芯片的基本单元，FPGA芯片的主要部分是由PLB和相对较少的其他模块（如IP）组成的阵列。PLB除了可以实现基本的组合逻辑查找表和时序逻辑功能外，还提供了专用的快速进位链，以执行快速算术加法和减法。例如，上海安路的PH1系列FPGA芯片的每个PLB包含8个SLICE单元，可以实现8个独立的LUT6查找表逻辑，也可以实现一个8比特位的进位链，并且可以级联纵向相邻的SLICE实现更宽比特位算术逻辑。上述宽比特位算术逻辑，组成了一个逻辑进位链Macro，在芯片自动化设计流程的后端布局时，需要连续占用纵向相邻的若干个SLICE。

解析式方法是目前工业界常用的集成电路布局方法之一。在采用解析式方法进行全局布局后，器件布局相互之间有可能存在着重叠，布局结果是不合法的。因此需要设计一个布局合法化算法，在合理的运行时间里，根据全局布局返回的初始布局位置将包括快速进位链Macro在内的所有器件的布局合法化（这里将问题简化为，所有器件布局相互之间没有重叠），同时尽可能保持全局布局的结果质量（即所有器件的合法化布局位置要尽量保持初始位置）。

三、赛题描述 

 

给定FPGA芯片包含M行N列的PLB阵列，每个PLB为宽、高都为8的正方形。每个PLB中包括8个纵向放置的SLICE,假设每个SLICE的宽、高分别为8和1。给定n个普通逻辑器件和进位链Macro （所有器件的宽度相同为8，普通逻辑器件的高度为1，进位链逻辑Macro的高度大于1），以及每个器件的初始布局位置（Xi Yi）（器件之间存在适度重叠）。求解器件的合法化布局位置（XXi YYi），满足下列条件（1）器件布局之间不存在重叠，并且（2）最小化器件布局移动的距离平方和：

 

式中的Wi是器件i的高度。

上海安路赛前将提供若干典型测例用于程序调试，以及网页来实时评测程序的结果质量（不公开）。测试用例的输入输出文件格式描述如下：

输入文件 case.in

文件第一行是PLB阵列的行列数M和N，和器件总个数n (1 <= n <= M*N)。之后的每一行是每个器件的高Wi (对进位链Macro，1 < Wi <= 1000；对于其他器件，Wi = 1)，以及左下角的初始坐标 Xi Yi ( 0 <= Xi < N , 0 <= Yi < M)。

输出文件 case.out

文件的每一行是按照输入文件中的给定顺序，每个器件的合法化布局坐标 XXi YYi ( 0 <= XXi < N , 0 <= YYi < M)。

样例

四、评分标准

技术评分标准主要包括程序质量评分，源代码和设计报告评分两部分。

1、程序质量评分（80分）

（1）基本要求

程序在合理运行时间（单线程）和内存，正常运行结束，输出格式正确合法，所有逻辑器件和进位链Macro的布局合法。

a)      运行时间上限：程序运行时间超出10m，认为程序死循环，程序质量得分为0分。程序运行时间上限会根据服务器环境和测例，有所调整。

b)      运行内存上限：运行内存超过10G，程序质量得分为0分。程序运行内存上限会根据服务器环境和测例，有所调整。

c)       优化目标上限：程序的优化目标值S超出最优结果（best_S）20%以上，程序质量得分为0。

（2）程序质量

要求竞赛方综合考虑优化目标和运行时间来选择算法。根据竞赛程序的优化目标值S和运行时间T，程序质量度量值Q计算如下：Q = S * (1 + T_factor),  T_factor  = 0.05 * log_2(T/median_T),并且T_factor的范围限定在[-0.1，0.1]，即根据运行时间有最大10%的结果质量调整。

所有竞赛程序中程序质量度量最小best_Q，得到满分（80分）。其他竞赛程序根据其程序质量度量值Q， 计算得分如下：80 - 160*(Q/best_Q - 1)。

2、源代码和设计报告评分（20分）

（1） 对于源代码，将对如下方面进行考察：（10分）

◆代码风格是否优美，组织架构是否清晰，可读性是否良好

◆有无良好的模块化设计

◆命名风格是否良好

 （2） 设计报告行文要求条理清楚，详略得当，清楚易读，内容应该包括以下几个方面：（10分）

a)      算法原理，测试结果

b)      时间/空间复杂度分析

c)       代码设计上其他亮点（如果有），比如架构设计，模块复用

关于更多大赛技术交流，请加入学生QQ群（792345737）